class Solution {
public:
/*
题目翻译：
字符串s是把abc...xyz绕成了一圈的环，然后p的子串如果在这圈26个字母的环里面能找到，那么这个p的子串就是有效的。
题目要求找出p所有的有效子串。 （并不是把p完成一圈！！！！！！！）
*/

    //运行超时
    //dp[i]表示，到i位置时，有多少不同非空子串也在 base 中出现。
    // int findSubstringInWraproundString(string s) {
    //     int n = s.size();
    //     vector<int> dp(n + 1);
    //     unordered_set<string> s_set;

    //     for (int i = 1; i < n + 1; i++)
    //     {
    //         int cnt = 0;
    //         for (int j = i; j >= 1; j--)
    //         {
    //             string tmp = s.substr(j - 1, i - j + 1);
    //             if (tmp.size() != 1 && !(s[j - 1] - s[j] == -1 || (s[j - 1] == 'z' && s[j] == 'a')))
    //                 break;

    //             if (!s_set.count(tmp))
    //             {
    //                 cnt++;
    //                 s_set.insert(tmp);
    //             }
    //         }

    //         dp[i] = dp[i - 1] + cnt;
    //     }

    //     return dp[n];
    // }


    //dp[i]表示，以i字符为结尾的所有字串，有多少个在base中出现
    /*
    以i位置为结尾的字串有两种情况:
        1. 单个字符s[i] -> 肯定会出现在base中 -> 个数为1
        2. 与字符s[i - 1]结尾的串拼接
            如果字符s[i]与字符s[i - 1]拼接而成的字串在base中，那就说明：
                如果以字符s[i - 1]结尾的串出现在base中，那么这些串以s[i]结尾，也会出现在base中
            -> 个数为dp[i - 1]
    因此，以i字符为结尾的所有字串，有多少个在base中出现 -> 1 + (dp[i - 1])

    假设题目没有给出条件“不同”，那么我们将以每一个字符结尾的字串在base中出现的次数相加即可，即将dp表中的数据相加
    但是由于给了“不同”，就需要去重：
        以字符串"abc"和"ghiabc"为例，显然，如果两个串以相同的字符结尾，取dp表中较大的即可
        由于只存在小写字符，因此开辟一个大小为26的整形空间，每个位置表示以该字符结尾的字串的最大个数
        最后将数组中的数据累加即可
    */
    int findSubstringInWraproundString(string s) {
        int n = s.size();
        vector<int> dp(n, 1);

        for (int i = 1; i < n; ++i)
        {
            if (s[i - 1] == 'z' && s[i] == 'a' || s[i - 1] + 1 == s[i])
                dp[i] += dp[i - 1];
        }

        int arr[26] = {0};
        for (int i = 0; i < n; ++i)
            arr[s[i] - 'a'] = max(arr[s[i] - 'a'], dp[i]);

        int ret = 0;
        for (auto i : arr)
            ret += i;

        return ret;
    }
};